We show that the problem k-Dominating Set and its several variants includingk-Connected Dominating Set, k-Independent Dominating Set, and k-DominatingClique, when parameterized by the solution size k, are W[1]-hard in eithermultiple-interval graphs or their complements or both. On the other hand, weshow that these problems belong to W[1] when restricted to multiple-intervalgraphs and their complements. This answers an open question of Fellows et al.In sharp contrast, we show that d-Distance k-Dominating Set for d >= 2 isW[2]-complete in multiple-interval graphs and their complements. We also showthat k-Perfect Code and d-Distance k-Perfect Code for d >= 2 are W[1]-completeeven in unit 2-track interval graphs. In addition, we present various newresults on the parameterized complexities of k-Vertex Clique Partition andk-Separating Vertices in multiple-interval graphs and their complements, andpresent a very simple alternative proof of the W[1]-hardness of k-IrredundantSet in general graphs.
展开▼
